package LongestIncreasingSubsequence;

import java.util.Comparator;
import java.util.TreeSet;



public class Solution {
	class Count{
		int val;
		int ans;
	}
    public int lengthOfLIS(int[] nums) {
        Comparator<Count> com=(c1,c2)->{
        	if (c1.val==c2.val) return Integer.compare(1,2);
        	return Integer.compare(c1.val, c2.val);
        };
        int result=0;
        TreeSet<Count> f=new TreeSet<Count>(com);
        Count[] f1=new Count[nums.length+1];
        for (int i=0;i<nums.length;i++){
        	Count newCount=new Count();
        	newCount.val=nums[i];
        	Count last=f.floor(newCount);
        	if (last==null) newCount.ans=1;
        	           else newCount.ans=last.ans+1;
        	if (f1[newCount.ans]==null){
        		f1[newCount.ans]=newCount;
        		f.add(newCount);
        	}
        	else
            if (f1[newCount.ans].val>newCount.val){
            	f1[newCount.ans].val=newCount.val;
            }
        	
        	result=Integer.max(result, newCount.ans);
        }
        return result;
        
    }
    
    public static void main(String args[]){
    	int[] t={10,9,2,5,3,7,101,18};
    	Solution so=new Solution();
    	System.out.println(so.lengthOfLIS(t));
    }
    
}
